class Solution:
    """
    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
    示例 1：
        输入：digits = "23"
        输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
    """

    def letterCombinations(self, digits: str):
        d = {
            '2': 'abc',
            '3': 'def',
            '4': 'ghi',
            '5': 'jkl',
            '6': 'mon',
            '7': 'pqrs',
            '8': 'tuv',
            '9': 'wxyz'
        }
        num = list(digits)
        tem = []
        ans = []

        def backtracking(height):
            if len(tem) == len(num):
                s = ''.join(tem)
                if s is "": return
                ans.append(s)
                return
            for i in d[num[height]]:
                tem.append(i)
                backtracking(height + 1)
                tem.pop()
            return ans

        backtracking(0)
        return ans
